package leetcode_900;

import java.util.ArrayList;
import java.util.List;

import helpclass.TreeNode;

/**
 *@author 周杨
 *IncreasingOrderSearchTree_897 将一颗二叉树转换成只有右子树的 中序遍历树
 *describe:
 *2018年10月14日 下午9:44:50
 */
public class IncreasingOrderSearchTree_897 {
	List<Integer> list;
	public TreeNode increasingBST(TreeNode root) {
		if(root==null)
			return null;
        this.list=new ArrayList<Integer>();
        help(root);
        root.val=list.get(0);//保证了起码有一个元素
        root.left=null;
        TreeNode run=root;
        for(int i=1;i<list.size();++i) {
        	run.right=new TreeNode(list.get(i));
        	run=run.right;
        }
        return root;
        
    }
	
	public void help(TreeNode root){
		if(root==null)
			return ;
		help(root.left);
		this.list.add(root.val);
		help(root.right);
	}
	
	
	TreeNode ret;
    public TreeNode increasingBST1(TreeNode root) {
        TreeNode ans = new TreeNode(-1);
        ret = ans;
        inorder(root);
        return ans.right;
    }
    
    public void inorder(TreeNode node) {
        if (node == null) {
            return;
        }
        
        inorder(node.left);
        node.left = null;
        ret.right = node;
        ret = ret.right;
        inorder(node.right);
    }
}
